package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.TreeNode;

/**
 * @author jinhu
 * created 2021-06-25 14:03
 */
public class Solution_0110 {
    /**
     * 判断它是否是高度平衡的二叉树
     * 一颗树平衡的条件，它的左子树的高度于右子树的高度相差为1，它子树的左右子树高度也是高度相差为1
     * 即左子树是否平衡，右子树是否平衡，左右子树高度相差不超过1
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return this.ifBalances(root).isBalance;
    }

    class ResultData {
        public boolean isBalance;
        public int height;

        public ResultData(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public ResultData ifBalances(TreeNode root) {
        if (root == null) {
            return new ResultData(true, 0);
        }
        ResultData resultDataleft = ifBalances(root.left);
        if (!resultDataleft.isBalance) {   //左子树不平衡
            return new ResultData(false, 0);
        }
        ResultData resultDataright = ifBalances(root.right);
        if (!resultDataright.isBalance) {   //右子树不平衡
            return new ResultData(false, 0);
        }
        if (Math.abs(resultDataleft.height - resultDataright.height)>1){   //左右子树高度是否相差1
            return new ResultData(false, 0);
        }
        return new ResultData(true, Math.max(resultDataleft.height , resultDataright.height) + 1);
    }
}
